#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<functional>
using namespace std;
int maxMoves(vector<vector<int>>& grid) {
	int m = grid.size(), n = grid[0].size();
	int dx[3] = { -1,0,1 };
	vector<vector<int>> memory(m, vector<int>(n, -1));
	function<int(int, int)> dfs = [&](int i, int j)->int
	{
		int path = 0;
		for (int k = 0; k < 3; k++)
		{
			int x = i + dx[k], y = j + 1;
			if (x < m && x >= 0 && y<n && grid[x][y] > grid[i][j])
			{
				if (memory[x][y] != -1)
					path = max(path, memory[x][y]);
				else
				{
					memory[x][y] = dfs(x, y) + 1;
					path = max(path, dfs(x, y) + 1);
				}
			}
		}
		return path;
	};
	int ret = 0;
	for (int i = 0; i < m; i++)
	{
		ret = max(ret, dfs(i, 0));
	}
	return ret;
}
int closedIsland(vector<vector<int>>& grid) {
	int m = grid.size(), n = grid[0].size();
	int dx[4] = { 0,0,1,-1 }, dy[4] = { 1,-1,0,0 };
	vector<vector<bool>> visited(m, vector<bool>(n, false));
	auto bfs = [&](int i, int j)
	{
		queue<pair<int, int>> q;
		q.push({ i,j });
		visited[i][j] = true;
		while (!q.empty())
		{
			auto [x1, y1] = q.front();
			q.pop();
			for (int k = 0; k < 4; k++)
			{
				int x2 = x1 + dx[k], y2 = y1 + dy[k];
				if (x2 >= 0 && x2 < m && y2 >= 0 && y2 < n
					&& visited[x2][y2] == false && grid[x2][y2] == 0)
				{
					visited[x2][y2] = true;
					q.push({ x2,y2 });
				}
			}
		}
	};
	for (int i = 0; i < m; i++)
	{
		if (grid[i][0] == 0 && visited[i][0] == false)
			bfs(i, 0);
		if (grid[i][n - 1] == 0 && visited[i][n - 1] == false)
			bfs(i, n - 1);
	}
	for (int j = 0; j < n; j++)
	{
		if (grid[0][j] == 0 && visited[0][j] == false)
			bfs(0, j);
		if (grid[m - 1][j] == 0 && visited[m - 1][j] == false)
			bfs(m - 1,j);
	}
	int ret = 0;
	for (int i = 1; i < m - 1; i++)
	{
		for (int j = 1; j < n - 1; j++)
		{
			if (grid[i][j] == 0 && visited[i][j] == false)
			{
				bfs(i, j);
				ret++;
			}
		}
	}
	return ret;
}
int main()
{

	return 0;
}